Двойственная задача

Двойственная задача [dual problem] , другие названия — сопряженная, обратная задача, одно из фундаментальных понятий теории линейного программирования — инструмент, позволяющий установить, оптимально ли данное допустимое решение задачи ЛП без непосредственного сравнения его со всеми остальными допустимыми решениями.

К каждой задаче линейного программирования можно построить своего рода симметричную: функционалы оптимальных решений у обеих задач совпадают, но если в прямой задаче они отражают наиболее эффективную комбинацию ресурсов, которая дает максимум целевой функции, то в другой, двойственной — наиболее эффективную комбинацию расчетных цен (оценок) ограниченных ресурсов. Это такие цены, при которых полученная продукция оправдывает затраты, а технологические способы, не включенные в план, по меньшей мере не более рентабельны, чем примененные. (Впрочем, хотя и принято считать прямой задачу, ориентированную на максимум целевой функции, а двойственной — ориентированную на минимум, на самом деле эти обозначения условны: обе задачи абсолютно равноправны, любую можно принять за прямую и искать к ней двойственную.)

Д.з. состоит в минимизации затрат при заданных лимитах ресурсов и формулируется следующим образом (в обозначениях, приведенных в статье «Линейное программирование«):

Найти набор переменных v₁, v₂, … v_n (называемых разрешающими множителями, объективно обусловленными (оптимальными) оценками, двойственными ценами и т.п.), минимизирующий линейную функцию  при том условии, что каждый включенный в план вид продукции рентабелен (полученная продукция оправдывает затраты), а не включенные в план — не более рентабельны, чем первые. Математически это условие можно записать так: (где j = 1, …, n)  для включенных в план и не больше нуля — для отброшенных при решении задачи.

Оценки характеризуют влияние свободных членов ограничений прямой задачи на оптимальную величину целевой функции. Иначе говоря, они показывают относительный вклад каждого ресурса в достижение оптимума; небольшое изменение количества ресурса изменяет оптимальное значение пропорционально величине оценки.